package com.lisp.algorithm.test.sort;

import java.util.Arrays;

public class RadixSort {

	public static void main(String[] args) {
		int data[] = {109, 9, 19, 8, 27, 45, 9, 10, 2, 89, 28, 43, 2, 7, 9, 190, 9, 9, 0};
		
		System.out.println(Arrays.toString(radixSort(data, 3)));
	}
	
	private static int[] radixSort(int a[], int bits) {
		int ret[] = a;
		for(int i=0, exp=1; i<bits; i++, exp=exp*10) {
			ret = countSort(ret, 9, exp);
			System.out.println(Arrays.toString(ret));
		}
		return ret;
	}
	
	private static int[] countSort(int a[], int maxVal, int exp) {
		int tmp[] = new int[maxVal+1];
		for(int x : a) {
			tmp[(x/exp) % 10]++;
		}
		
		for(int i=1; i<maxVal+1; i++) {
			tmp[i] = tmp[i-1] + tmp[i]; 
		}
		
		int ret[] = new int[a.length];
		for(int i=a.length-1; i>-1; i--) {
			int radixVal = (a[i]/exp) % 10;
			ret[tmp[radixVal]-1] = a[i];
			tmp[radixVal]--;
		}
		
		return ret;
	}
}
